1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
const int maxn = 3005;
const int mo = 1e9 + 7;
using namespace std;
int f[2][maxn], s[maxn], Max[maxn];
int n, m;
int main(){
scanf("%d%d", &n, &m); getchar();
for (int i = 1; i <= n; i++) s[i] = s[i - 1] + getchar() - '0';
for (int l, r, i = 1; i <= m; i++){
scanf("%d%d", &l, &r);
Max[l] = max(Max[l], r);
}
for (int i = 1; i <= n; i++) Max[i] = max(i, max(Max[i], Max[i - 1]));
f[0][0] = 1; int T = 1;
for (int i = 1; i <= n; T ^= 1, i++){
memset(f[T], 0, sizeof f[T]);
for (int j = 0; j <= n; j++){
if (j + s[Max[i]] - s[Max[i - 1]] > 0) (f[T][j - 1 + s[Max[i]] - s[Max[i - 1]]] += f[T ^ 1][j]) %= mo;
if (j + s[Max[i]] - s[Max[i - 1]] < Max[i] - (i - 1)) (f[T][j + s[Max[i]] - s[Max[i - 1]]] += f[T ^ 1][j]) %= mo;
}
}
printf("%d\n", f[T ^ 1][0]);
return 0;
}
|